public class Solution01 {
	//思路：用计数器记录当前层和下一层的结点数
	public List<Integer> largestValues(TreeNode root){
		ArrayList<Integer> maxValues = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		//当前层结点数 
		int currentNum = 0;
		//下一层结点数
		int nextNum = 0;
		//设置为Java提供的最小值
		int maxVal = Integer.MIN_VALUE; 
		boolean isFirst = true;

		if(root == null){
			return maxValues;
		}
		queue.offer(root);
		currentNum = 1;
		while(!queue.isEmpty()){
			TreeNode curNode = queue.poll();
			currentNum--;
			//选每层的最值
			if(isFirst){
				maxVal = curNode.val;
				isFirst = false;
			} else {
				//maxVal = curNode.val > maxVal ? curNode.val : maxVal;
				maxVal = Math.max(curNode.val, maxVal);
			}
			//判断左右子树
			if(curNode.left != null){
				queue.offer(curNode.left);
				nextNum += 1;
			}
			if(curNode.right != null){
				queue.offer(curNode.right);
				nextNum++;
			}
			//最值
			if(currentNum == 0){
				//System.out.println("nextNum = " + nextNum);
				maxValues.add(maxVal);
				currentNum = nextNum;
				nextNum = 0;
				isFirst = true;
			}
		}
		return maxValues;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(){}
	TreeNode(int val){ this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}
